package org.example.myleet.p992;

public class Solution {

    int[] digitCount;

    int kCount, l, r, n, result;

    /**
     * 178 ms
     * 双指针模拟法
     */
    public int subarraysWithKDistinct(int[] A, int K) {
        if (A.length == 1) {
            return 1;
        }
        n = A.length;
        digitCount = new int[n+1];
        kCount = 0;
        l = 0;
        r = 0;
        result = 0;
        for (int i=l; i<K; i++) {
            rForward(A);
        }
        outer:
        while (r <= n) {
            if (r-l < K && r >= n) {
                //右指针超出数组且子数组长度已不足K长度，结束
                break;
            }
            while (kCount < K) {
                if (r >= n) {
                    //右指针超出数组且子数组长度但子数组中的不同数个数仍不足K，结束
                    break outer;
                }
                rForward(A);
            }
            ++result;
            if (r >= n || digitCount[A[r]] < 1) {
                //右指针到右边界或者右指针上的数在子数组中不存在，此时需要将左指针右移前进，并重置窗口大小为K
                --digitCount[A[l]];
                if (digitCount[A[l]] < 1) {
                    --kCount;
                }
                ++l;
                while (r-l > K) {
                    --r;
                    --digitCount[A[r]];
                    if (digitCount[A[r]] < 1) {
                        --kCount;
                    }
                }
            } else {
                //右指针上的数在子数组中存在，可以扩大窗口
                rForward(A);
            }
        }
        return result;
    }

    /**
     * 右指针右移（前进）
     */
    private void rForward(int[] A) {
        if (digitCount[A[r]] < 1) {
            ++kCount;
        }
        ++digitCount[A[r]];
        ++r;
    }
}
